package VacationHomework.LeetCode;

public class NewCoder_NC32 {
    public int sqrt (int x) {
        if(x==1){
            return 1;
        }
        int left=1;
        int right=x;
        while (right>=left){
           int mid=(left+right)/2;
           if(mid<=x/mid &&(mid+1)>x/(mid+1) ){  //mid*mid可能会溢出，所以采用除法
             return mid;
           }else if(mid<x/mid){
               left=mid+1;
           }else {
               right=mid-1;
           }
        }
        return 0;
    }
}
